#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-01 9:02 上午
# @Author  : yangdy
# @File    : 2020-09-01.486.预测赢家
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:

        # def dfs(s, e, t):
        #     if s == e:
        #         return t * nums[s]
        #     ss = nums[s] * t + dfs(s + 1, e, -t)
        #     se = nums[e] * t + dfs(s, e - 1, -t)
        #     return max(ss * t, se * t) * t
        #
        # return dfs(0, len(nums)-1, 1) >= 0
        n = len(nums)
        dp = [[0] * n for i in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        return dp[0][n-1] >= 0


questions = [
    ([1, 5, 2], ),
    ([1, 5, 233, 7], ),
]

work(questions, lambda q: Solution().PredictTheWinner(q[0]))

# aa = [0] * 10
#
# print(aa)
# aa[0] = 2
# print(aa)
